import java.util.HashMap;
import java.util.Map;

public class Solution1005 {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Map<Integer,Integer> map=new HashMap<>();
        int total=0;
        for (int num : nums) {
            total+=num;
            map.put(num,map.getOrDefault(num,0)+1);
        }
        for (int i=-100;i<0;i++){
            int times=Math.min(k,map.getOrDefault(i,0));
            if (times!=0) {
                total += 2 * (-i) * times;
                map.put(i, 0);
                map.put(-i, times);
                k = k - times;
            }
            if (k==0){
                break;
            }
        }
        if (k>0 && k%2==1 && !map.containsKey(0)){
            for (int i=1;i<=100;i++){
                if (map.containsKey(i)){
                    total-=i*2;
                    break;
                }
            }
        }
        return total;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1005().largestSumAfterKNegations(new int[]{4,2,3},1));
    }
}
